package leetcode_acm.leetcode_1;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * 功能描述
 *
 * @author: 张庭杰
 * @date: 2023年03月13日 22:53
 */
public class FindMode {

    class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }

    public int[] findMode(TreeNode root) {
        if(root == null){
            return new int[]{};
        }
        TreeNode prev = null;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        int maxCount = 0;
        int count = 0;
        List<Integer> list = new ArrayList<>();
        while(cur != null || !stack.isEmpty()){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            if(prev != null && prev.val != top.val){
                count = 1;
            }
            if(prev != null && prev.val == top.val){
                count++;
            }
            if(maxCount == count){
                list.add(top.val);
            }
            if(count > maxCount){
                list.clear();
                list.add(top.val);
                maxCount = count;
            }
            prev = top;
            cur = top.right;
        }
        int n = list.size();
        int [] ans = new int[n];
        for(int i = 0;i<n;i++){
            ans[i] = list.get(i);
        }
        return ans;
    }
}
